/**
 * //You are given an integer array nums and an integer target.
 * //
 * // You want to build an expression out of nums by adding one of the symbols '+'
 * //and '-' before each integer in nums and then concatenate all the integers.
 * //
 * //
 * // For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1
 * //and concatenate them to build the expression "+2-1".
 * //
 * //
 * // Return the number of different expressions that you can build, which
 * //evaluates to target.
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: nums = [1,1,1,1,1], target = 3
 * //Output: 5
 * //Explanation: There are 5 ways to assign symbols to make the sum of nums be
 * //target 3.
 * //-1 + 1 + 1 + 1 + 1 = 3
 * //+1 - 1 + 1 + 1 + 1 = 3
 * //+1 + 1 - 1 + 1 + 1 = 3
 * //+1 + 1 + 1 - 1 + 1 = 3
 * //+1 + 1 + 1 + 1 - 1 = 3
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: nums = [1], target = 1
 * //Output: 1
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // 1 <= nums.length <= 20
 * // 0 <= nums[i] <= 1000
 * // 0 <= sum(nums[i]) <= 1000
 * // -1000 <= target <= 1000
 * //
 * //
 * // Related Topics 数组 动态规划 回溯 👍 1326 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00494TargetSum {
    public static void main(String[] args) {

        Solution solution = new ID00494TargetSum().new Solution();


        System.out.println(solution.findTargetSumWays(new int[]{0, 0, 0, 0, 0, 0, 0, 0, 1}, 1));

    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int findTargetSumWays(int[] nums, int target) {

            //cal sum of the nums, if sum < target return 0;
            //1. 先求一个sum，因为nums中全是正整数，sum表示 nums中所有的数字能达到的最远状态
            int sum = sumNums(nums);
            if (sum < Math.abs(target)) {
                return 0;
            }
            //2. 定义status数组，纵列表示第几步，横列表示状态值。因为能达到的状态可以为[-sum , +sum]，左开右开。所以status[i].length需要初始化为 2*sum + 1
            int statusLength = 2 * sum + 1;
            int[][] status = new int[nums.length][statusLength];

            //3. 初始化第一行，可达状态是 +nums[0] 和 -nums[0], 因为数组下标无法用负数表示，集体便宜一个+sum；
            if (Math.abs(-nums[0] + sum) <= sum) {
                status[0][-nums[0] + sum] += 1; //负号，

            }
            if (Math.abs(nums[0] + sum) < statusLength) {
                status[0][nums[0] + sum] += 1; //正号
            }
            //4. 开始动态求解，当前行的状态等于 能到达当前状态的上一行状态的状态之和。
            // status[i][j - nums[i]] += status[i-1][j]; //来自负号
//       //status[i][j + nums[i]] += status[i-1][j]; //来自正号
//
            for (int i = 1; i < nums.length; i++) { //每一步开始记录
                for (int j = 0; j < status[i].length; j++) {
                    if (status[i - 1][j] > 0) {
                        if (j - nums[i] >= 0) {
                            status[i][j - nums[i]] += status[i - 1][j]; //来自负号
                        }

                        if ((j + nums[i]) < status[i].length) {
                            status[i][j + nums[i]] += status[i - 1][j]; //来自正号
                        }

                    }


                }

            }

            //5. 最后获取只需要看最后一行，target + sum（偏移）中，最终的路线之和

            return status[nums.length - 1][target + sum];


        }


        public int sumNums(int[] nums) {
            int sum = 0;
            for (int n : nums) {
                sum += n;

            }

            return sum;

        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}